前言

在前面介紹 RSA 時，我們看到密碼學如何利用大數分解（Integer Factorization）的算力不對稱性，建立了公開金鑰體系。然而，RSA 的金鑰長度動輒需要 2048 到 4096 位元，才能抵禦現代電腦的破解。

為了解決金鑰過長與傳輸負擔問題，現代密碼學轉向了效率更高的橢圓曲線密碼學（Elliptic Curve Cryptography, ECC）。ECC 能以 256 位元的金鑰達到與 3072 位元 RSA 同等的安全強度。

但 ECC 不是把 RSA 的公式換個變數而已，它建立在更為抽象且嚴謹的代數結構之上。在正式畫出橢圓曲線之前，我們必須先搭建好承載這套體系的「代數舞台」——有限域（Finite Field）、群論（Group Theory） 與 離散對數難題（Discrete Logarithm Problem, DLP）。

一、 密碼學的邊界：為什麼需要有限域（Finite Field）？

實數世界 R 具備連續性與無窮性，但在電腦工程與密碼學中，實數有兩個致命缺點：

1. 浮點數精度誤差：電腦無法精準儲存無理數，捨入誤差會直接摧毀密碼學的精確還原能力。
2. 資訊狀態無法列舉：無限大且連續的空間無法提供離散的狀態空間來隱藏資訊。

密碼學需要的是一個範圍有限、運算精準且封閉的數字空間，這就是有限域（Finite Field，又稱 Galois Field, GF）。

1. 質數有限域 GF(p)

在 ECC 中，最常使用的有限域是質數有限域 GF(p)，其中 p 為一個極大的質數。
GF(p) 包含 p 個整數元素：

GF(p) = {0, 1, 2, 3, ..., p - 1}

這個集合中的所有加法、減法、乘法運算，皆在模 p（mod p） 的規則下進行，確保任何運算結果永遠不會超出這個集合。

2. 有限域中的四則運算與「除法」

加法、減法與乘法在模運算下非常直觀，但有限域中的「除法」 該如何處理？

在有限域 GF(p) 中，不存「小數」或「分數」。當我們寫下 a ÷ b (mod p) 時，其本質是找到一個整數 x，滿足：

b * x ≡ a (mod p)

換句話說，有限域中的除法，定義為乘以「模乘法反元素（Modular Multiplicative Inverse）」：

a ÷ b ≡ a * b^{-1} (mod p)

其中 b^{-1} 為 b 在模 p 下的乘法反元素，滿足 b * b^{-1} ≡ 1 (mod p)。

3. 為什麼模數 p 必須是質數？

因為根據數論，當且僅當 gcd(b, p) = 1 時，b 才存在模乘法反元素。若 p 為質數，則集合內所有非零整數 {1, 2, ..., p-1} 都與 p 互質！這保證了在 GF(p) 中，除了除以 0 之外，任何非零元素皆可安全執行除法運算。

4. 算例演練：在 GF(7) 中做除法

設有限域 GF(7) = {0, 1, 2, 3, 4, 5, 6}，求 4 ÷ 3 mod 7：

• Step 1：求解 3^{-1} mod 7
  尋找一個數字 x ∈ GF(7) 使 3 * x ≡ 1 (mod 7)。
• 3 * 1 = 3 ≡ 3
• 3 * 5 = 15 = 2 * 7 + 1 ≡ 1 (mod 7)
• 得知 3^{-1} ≡ 5 (mod 7)。
• Step 2：將除法轉為乘法

4 ÷ 3 ≡ 4 * 3^{-1} ≡ 4 * 5 = 20 (mod 7)

20 mod 7 = 6

• 驗證結果：6 * 3 = 18 = 2 * 7 + 4 ≡ 4 (mod 7)（完全正確！）。

二、 抽象代數的靈魂：什麼是群（Group）？

有限域為我們提供了數字的「容器」，而群論（Group Theory） 則規定了元素之間「如何相互作用」。

1. 群（Group）的四大公理

一個集合 G 搭配一種二元運算符號 。 構成的代數結構 (G, 。)，若要被稱為一個群（Group），必須嚴格滿足以下四大公理：

若該群運算還滿足交換律（∀ a, b ∈ G, a 。 b = b 。 a），則稱為阿貝爾群（Abelian Group） 或可交換群。

2. 循環群（Cyclic Group）與生成元（Generator）

若群 G 中的所有元素，都可以由某個特定元素 g ∈ G 透過重複進行群運算所生成：

G = {g^1, g^2, g^3, ..., g^n}

則稱 G 為一個循環群，而 g 被稱為該群的生成元（Generator），最小的次方數 n 稱為該群的階數（Order）。

循環群是密碼學中最完美的結構，因為只要拿到生成元 g，就能透過指數或純量乘法，有規律地遍歷整個群空間。

三、 單向陷門的數學核心：離散對數難題（DLP）

公鑰密碼學的底層邏輯，永遠在尋找一種「正向計算極快，反向推導極難」 的單向陷門函數（Trapdoor One-Way Function）。

在模運算構成的循環群中，這種單向性體現為離散對數難題（Discrete Logarithm Problem, DLP）。

[ 正向運算：模指數 (Easy) ]
  底數 g ─┐
  指數 x ─┼─>  y = gˣ mod p  ───(毫秒級計算完成)───> 輸出結果 y
  模數 p ─┘

[ 反向推導：離散對數 (Hard) ]
  已知 y, g, p  ───> 求解 x = log_g (y) mod p  ───(古典電腦無法在有效時間解開)

1. 數值演練：感受離散對數的混亂性

設質數 p = 23，生成元 g = 5，私密指數 x = 6：

• 正向計算（模指數運算）：

y = g^x mod p = 5^6 mod 23

• 5^1 = 5 (mod 23)
• 5^2 = 25 ≡ 2 (mod 23)
• 5^3 = 2 * 5 = 10 (mod 23)
• 5^6 = (5^3)^2 = 10^2 = 100 ≡ 8 (mod 23)
• 正向求出 y = 8，利用快速模指數演算法（Square-and-Multiply）只需 \mathcal{O}(\log x) 次運算。
• 反向推導（離散對數）：
  給定 5^x ≡ 8 (mod 23)，求 x。
  在實數世界中，我們可以利用連續對數函數求得 log_5 8 ≈ 1.29。但在模運算構成的離散空間中，數值分佈如同雜亂無章的亂數串，沒有連續微積分的幾何規律可循。
  唯一的破解方式只有逐個代入嘗試（暴力窮舉）。當 p 選取為 2048 位元的大質數時，狀態空間高達 2^{2048}，古典電腦將耗費數十億年也無法算完。